Shape skeletons are powerful geometry abstractions that provide useful intermediate representations for a number of geometric operations on solid models, including feature recognition, shape decomposition, finite element mesh generation, and shape synthesis. In this context, the skeleton of an object consists of the closure of a locus of spheres that are maximally inscribable in the object so that points on the skeleton are minimally equidistant from at least two points on the boundary of the object. Skeletons of solids generically comprise a collection of two-dimensional (2D) surface patches, but can also contain one-dimensional (1D) curve components (or even zero dimensional points, if the object is composed of disjoint spheres).
The skeleton concept was formally introduced by H. A. Blum as a tool for shape description (described in "A Transformation for Extracting New Descriptors of Shape," Models for the Perception of Speech and Visual Form, ed. W. Wathen-Dunn, MIT Press, 1967, pp. 362-381) and has since been extended to three dimensions by others. The mathematical properties of skeletons and some of their curvature properties are known in the art. The importance of skeletons for the applications mentioned above has led to an extensive body of related literature describing algorithms and implementations for skeleton generation.
The techniques for generating skeletons can be classified into five categories. The first category includes algorithms that employ the exact mathematical description of the object without relying on discretization of either the object or the embedding space. The prior art discusses 2D and 3D algorithms for continuous skeleton generation. For example, one such reference presents a skeleton generation method for convex polyhedra. While these methods are appealing because they produce exact skeletal curves and surfaces, the algebraic manipulations involved for computing geometric intersections currently limit their applicability to low degree curves and surfaces.
The second category involves discretization of the space in which an object for which a skeleton is being constructed lies, using quadtrees, octrees, etc., and employs thinning procedures for the skeleton generation. This approach has become popularized by the computer vision community because of the discrete image input typical of vision processing. While space discretization is very effective in 2D applications, the size of the 3D grids required for non-trivial solids becomes prohibitive. U.S. Pat. No. 5,390,291 discloses how skeletons are applied for shape interpolation in a voxel based setting, but the skeletons are computed for 2D image data (using a thinning algorithm) and not for the 3D voxel description of a solid.
The third category involves tracing algorithms to traverse skeleton curves. This approach is effective for general 2D objects and 3D polyhedra, but extensions to non-polyhedral objects have not appeared in the prior art.
The fourth category involves transforming skeleton generation into the numerical solution of variational problems or PDEs to track the propagation of a moving front. Specific prior art approaches include the use of active contours (or snakes) and modified eikonal equations. Although these methods can exploit sophisticated numerical techniques, the computational requirements exceed current hardware capabilities for non-trivial 3D objects.
The fifth category employs discretization or sampling of the object's boundary and uses Voronoi diagrams as the basis for skeleton generation. These discretization methods produce a polygonal approximation that converges to the skeleton as the sampling becomes very dense, but the convergence is slow, especially near the edge of the skeleton of an object bounded by curved surfaces.
From the foregoing discussion, it will be apparent that a more efficient, accurate technique for producing skeletons would be useful in modeling objects. Of the five approaches discussed above, a variation of the fifth appears to offer the desired effectiveness. Details of this technique are discussed by Munikumar S. Vimawala in a Master's Thesis entitled, "Computational Procedures for Topological Shape Design," which was published in 1994. However, a more accurate determination of the skeleton of 3D objects is required than is disclosed in this prior art reference, since the disclosed approach produces only approximate skeletons having significant errors.